#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <vector>
#include<algorithm>
#include<set>
using namespace std;
int maxArea(vector<int>& height) 
{
	int left = 0, right = height.size() - 1;
	int ret = 0;
	while (left < right)
	{
		int h = min(height[left], height[right]);
		int a = right - left;
		ret = max(a * h, ret);
		if (height[left] < height[right])
		{
			left++;
		}
		else
		{
			right--;
		}
	}
	return ret;
}
int triangleNumber(vector<int>& nums) 
{
	sort(nums.begin(), nums.end());
	int i = nums.size() - 1;
	int ret = 0;
	while (i > 1)
	{
		int right = i - 1, left = 0;
		while (left < right)
		{
			if (nums[left] + nums[right] <= nums[i])
			{
				ret += right - left;
				right--;
			}
			else
			{
				left++;
			}
		}
		i--;
	}
	return ret;
}
vector<int> twoSum(vector<int>& price, int target) 
{
	sort(price.begin(), price.end());
	int left = 0, right = price.size() - 1;
	while (left < right)
	{
		if (price[left] + price[right] == target)
		{
			return { price[left],price[right] };
		}
		else if (price[left] + price[right] > target)
		{
			right--;
		}
		else
		{
			left++;
		}
	}
	return { 0,0 };
}
vector<vector<int>> threeSum(vector<int>& nums) 
{
	sort(nums.begin(), nums.end());
	int i = nums.size() - 1;
	vector<vector<int>> vv;
	while (i > 1)
	{
		int left = 0, right = i - 1;
		int target = -nums[i];
		while (left < right)
		{
			if (nums[left] + nums[right] == target)
			{
				vector<int> v = { nums[left],nums[right],nums[i] };
				vv.push_back(v);
				right--;
				left++;
			}
			else if (nums[left] + nums[right] > target)
			{
				right--;
			}
			else
			{
				left++;
			}
		}
		i--;
	}
	set<vector<int>> s;
	for (auto& e : vv)
	{
		s.insert(e);
	}
	vv.clear();
	for (auto& e : s)
	{
		vv.push_back(e);
	}
	return vv;
}
vector<vector<int>> fourSum(vector<int>& nums, int target) 
{
	vector<vector<int>> vv;
	sort(nums.begin(), nums.end());
	int i = nums.size() - 1;
	while (i > 2)
	{
		int j = i - 1;
		while (j > 1)
		{
			int tmp = target - nums[i] - nums[j];
			int left = 0, right = j - 1;
			while (left < right)
			{
				if (nums[left] + nums[right] == tmp)
				{
					vector<int> v = { nums[left],nums[right],nums[j],nums[i]};
					vv.push_back(v);
					right--;
					left++;
				}
				else if (nums[left] + nums[right] > tmp)
				{
					right--;
				}
				else
				{
					left++;
				}
			}
			j--;
		}
		i--;
	}
	set<vector<int>> s;
	for (auto& e : vv)
	{
		s.insert(e);
	}
	vv.clear();
	for (auto& e : s)
	{
		vv.push_back(e);
	}
	return vv;
}
int main()
{
	vector<int> v = { 4,2,3,4 };
	cout << triangleNumber(v);
	return 0;
}
